package main

/*
	在给定网格中，每个单元格可以有以下三个值
	0代表空单元格，1代表新鲜橘子，2代表腐烂的橘子
	每分钟，任何与腐烂的橘子(在4个正方向上)相邻的新鲜橘子都会腐烂
	返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回-1
*/
var(
	ddddx = [4]int{0,0,-1,1}
	ddddy = [4]int{-1,1,0,0}
)
func orangesRotting(grid [][]int) int{
	minute := 0
	// 将腐烂的橘子放入队列中
	queue := [][]int{}
	m := len(grid)
	n := len(grid[0])
	for i:=0;i<m;i++{
		for j:=0;j<n;j++{
			if grid[i][j]==2{
				queue = append(queue,[]int{i,j})
				grid[i][j]=3
			}
		}
	}
	for len(queue)>0{
		orange := queue[0]
		queue = queue[1:]
		// 遍历上下左右
		for i:=0;i<4;i++{
			newx := ddddx[i]+orange[0]
			newy := ddddy[i]+orange[1]
			if newx>=0&&newx<m&&newy>=0&&newy<n&&grid[newx][newy]==1{
				//新鲜橘子腐烂
				grid[newx][newy]=grid[orange[0]][orange[1]]+1
				// 新橘子入队
				queue = append(queue,[]int{newx,newy})
				minute = grid[newx][newy]-3
			}
		}
	}
	//如果还有新鲜橘子，返回-1
	for i:=0;i<m;i++{
		for j:=0;j<n;j++{
			if grid[i][j]==1{
				return -1
			}
		}
	}
	return minute
}

func main(){
	grid := [][]int{
		{0,2},
	}
	print(orangesRotting(grid))
}
